1. Field of the Invention
The present invention relates to a device for encoding and/or decoding of a Huffman code which is a variable-length code.
2. Related Background Art
Compression technologies for the digital signals are showing remarkable progresses in recent years, and methods proposed by JPEG (Joint Photographic Exterts Group) and MPEG (Moving Picture Exterts Group) are becoming accepted as world-wide standards for compressing digitized still and moving image signals.
In these compressing methods, the image signal is at first orthogonally transformed by DCT (discrete cosine transformation), then the amount of information is reduced by eliminating the signal components of the visually inconspicuous portions in thus transformed signal, and the information is further compressed by Huffman encoding.
In the Huffman encoding, the codes of variable length are assigned according to the frequency of appearance of the codes. The amount of information can be compressed by the assignment of a code of a shorter bit length to the code of a higher frequency of appearance.
In the decoding of thus encoded Huffman codes with a table, the memory capacity required for the table inversely proportional to the speed of decoding. Consequently there can be conceived two opposite approaches which are:
a) a method of reducing the memory capacity for the table, though the process speed is low; and
b) a method of increasing the process speed though a larger memory capacity is required for the table.
An extreme case of the method (a) consists of decoding of 1 bit in each cycle, requiring several cycles for decoding a Huffman code. Such decoding method is cited as a conventional method in the Japanese Patent Laid-open Application No. 57-55668. On the other hand, an extreme case of the method (b) decodes a Huffman code in a cycle.
There can naturally be conceived other intermediate methods between these extreme cases, such as methods for decoding two or more bits in a cycle.
In all these conventional methods, the information of the Huffman code to be decoded is supplied, without conversion to another information, either directly into the table or a part of such information is supplied, in combination with information obtained by previous decoding, into the table.
FIG. 1 shows a conventional decoding device for decoding a Huffman code in a cycle, designed for decoding a Huffman code of a maximum code length of 16 bits into a fixed-length code of 8 bits.
In FIG. 1, there are shown a terminal 101 for entering the Huffman-encoded data, and a buffer 102 for temporarily storing the data. Since Huffman code is a variable-length code, the input data rate cannot be constant if the output data rate at the decoding is maintained constant, so that the above-mentioned buffer is required.
There are also provided an unpacking circuit 103 for connecting the data entered with a unit of m bits and obtaining the leading 16 bits after the removal of the already decoded data; a decoding table 104 for decoding a Huffman code in said 16-bits data; a terminal 105 for outputting the decoded fixed-length code (8 bits); and a 4-bits signal 106 indicating the bit length of the decoded Huffman code.
Said 4-bits signal 106 may represent the bit length itself or the bit length minus one, and FIG. 1 shows the latter case. A maximum code length of 16 bits requires 5 bits for direct representation, but, as a code length of 0 bit does not exist, a representation with 4 bits is made possible by indicating (code length xe2x88x921), namely by representing the code length of 1 bit with xe2x80x9c0000xe2x80x9d. However, there is no difference between the two methods if the maximum code length is not an exponent of 2. The signal 106 is supplied to the above-mentioned unpacking circuit 103, for eliminating the decoded data.
This example required the memory of a large capacity, as the decoding table 104 requires 64 kxc3x9712 bits or 96 kBytes.
Then, FIG. 2 shows the configuration in which the above-explained conventional example is applied to a decoding device for the JPEG codes. Also in case the JPEG codes, a Huffman code of a maximum code length of 16 bits is decoded into a fixed-length code of 8 bits (NNNN signal of 4 bits and SSSS signal of 4 bits), but additional bits are inserted between the Huffman codes and have to be removed at the decoding.
If the additional bits have a maximum bit length of 10 bits, the signal released from the unpacking circuit 200 shown in FIG. 2 becomes 26 bits. Among these 26 bits, the leading 16 bits are supplied to the decoding table 104 and are converted, as already explained with reference to FIG. 1, into a fixed-length code of 8 bits and code-length information 106 of 4 bits. On the other hand, the signal of 26 bits is also supplied to a shifter 201 for removal of the decoded Huffman code based on the code-length information (said removal being achieved by shifting said signal of 26 bits by said code length), and the leading 10 bits are supplied to a terminal 202. All said 10 bits do not constitute the signal of additional bits, but only the bits of an upper rank indicated by the SSSS signal output from the decoding table constitute said additional bits.
Thus, after the decoding of a Huffman code and before the decoding of a next Huffman code, it is required, in the configuration shown in FIG. 1, to remove the bits of the already decoded Huffman code by the unpacking circuit, but, in case of FIG. 2, to remove also the bits of the additional signal.
For this reason, the signal 106 indicating the code length of the Huffman code and a signal 203 (SSSS signal) indicating the bit length of the additional bits are added in an adder 204, and the result of the addition is supplied to the unpacking circuit 200 for removing the Huffman code and the additional bits in each cycle.
In the conventional example explained above, the high-speed decoding of the Huffman codes requires a large memory capacity for the decoding table, leading to the following drawbacks:
1) In forming the decoding device into an integrated circuit, the chip area becomes larger and requires a higher cost;
2) A long time is required for the rewriting of the decoding table; and
3) As the amount of information in the decoding table is large, it is not possible to effect optimum Huffman encoding for each information (for example image information) to be compressed. If such optimum encoding is conducted, the decreased information by compression has to be associated, for each image, with information on the decoding table, and such optimum encoding becomes meaningless because the amount of such associated information is quite large.
The object of the present invention is to reduce the memory capacity required for the decoding table, as such reduction of the memory capacity resolves all three drawbacks mentioned above.
The above-mentioned object can be attained, according to an embodiment of the present invention, by a Huffman encode/decoding device comprising means for comparing a Huffman code to be decoded with plural boundary values; means for identifying the bit length of said Huffman code from the result of comparison by the comparing means; means for determining the difference between the lower limit boundary value at the bit length and said Huffman code; and means for adding the difference to a code number corresponding to the boundary value, wherein the code number of said Huffman code is determined by calculation with the above-mentioned means, and the Huffman code is with a table for converting the code number to the original fixed-length code.